# coding: utf-8
'''
Created on 30/05/2013

@author: Vagner Clementino

Código fonte da questão 05 da lista 02 da disciplina Criptografia
'''
import math
from quadraticSieve.trial_division import trial_division



def is_p_smooth(lista_fatores,p,S):    

    t = len(lista_fatores)
    
    if (lista_fatores[t-1] > p):
        return False
     
    for p in lista_fatores:
        if (S.count(p) == 0):
            return False
    else:
        return True

     

def get_v(S,b):
    '''
        Retorna v, conforme descrito no Algoritmo 3.21 do HAC,
        onde S é base de primos utilizada no algoritmo e b = (x+m)^2 -n
    '''
    v = []
    
    if b < 0:
        v.append(1)
        b_fatorado = trial_division((-1) * b)
    else:
        v.append(0)
        b_fatorado = trial_division(b)
        
    t = len(S)
    
    for i in range(1,t):
        #Recuperando o numero de ocorrencias de S[i] em b fatorado
        ocorrencias = b_fatorado.count(S[i])
        #Adicionando em v o número de ocorrencias modulo 2
        ocorrencias = ocorrencias % 2
        v.append(ocorrencias)
    return v

def incrementa_x(x):
    if x == 0:
        novo_x = 1
    elif x < 0:
        novo_x = ( ( (-1) * x) + 1)
    else:
        novo_x = (-1) * x
    return novo_x
    
    
    
def quadratic_sieve(n):
    S = [-1,3,19,23,29,31,37]
    
    t = len(S)
    
    m = int(math.floor(math.sqrt(n)))
    
    tuplas = []
    x = 0
    
    for i in range(1,t+2):
        
        while True:
            b = ((x+m)**2 - n)
            #Recuperando a lista de fatores primos de break
            if b > 0:
                lista_fatores = trial_division(b)
            else:
                lista_fatores = trial_division((-1)*b)
            if(is_p_smooth(lista_fatores, S[(t-1)],S) == True):
                break
            else:
                x = incrementa_x(x)                
        a = (x + m)
        v = get_v(S, b)
        tupla_aux = (i,x,b,lista_fatores,a,v)
        tuplas.append(tupla_aux)
        x = incrementa_x(x)
    for tupla in tuplas:
        print(tupla)
        
        
                
            
            
 
 
 
 
 
            